package main

import "fmt"

//斐波那契数列
//1，1，2，3，5，8，13，21,34,55
//斐波那契数列 第n项等于(n-1)+(n-2)

//这是第一种递归方法
func fb(n int) int {
	if n == 1 || n == 2 {
		return 1
	}
	return fb(n-1) + fb(n-2)
}

//采用尾递归的方法求斐波那契数列
func fbn(n int, a int, b int) int {
	if n == 1 {
		return a
	}
	return fbn(n-1, b, a+b)
}

func main() {
	fmt.Println(fb(10))
	fmt.Println(fbn(10, 1, 1))
}
